\documentclass[a4paper]{article}
\usepackage[affil-it]{authblk}
\usepackage{indentfirst}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{geometry}
\usepackage{xeCJK}
\geometry{margin=1.5cm, vmargin={0pt,1cm}}
\setlength{\topmargin}{-1cm}
\setlength{\paperheight}{29.7cm}
\setlength{\textheight}{25.3cm}

\begin{document}
% ==================================================
\title{Numerical Analysis homework \# 2}

\author{周川迪 Zhou Chuandi 3220101409}
\affil{强基数学2201}

\date{\today}

\maketitle

\begin{abstract}
  2.11.1 Theoretical questions

  Complete question 2.11.1 I - XII on page 18 of the lecture notes in English. 

  Theorems or Corollaries are referred from \textit{handoutsNUMPDEs-2024-08-17}
\end{abstract}



\section*{I. Linear Interpolation and Error Estimation}
\subsection*{I-a}
We have $f(x)=\frac{1}{x}$, $f''(x)=\frac{2}{x^3}$ and $x_0=1,x_1=2,f_0=1,f_1=\frac{1}{2}$. Then,
\[p_1(f;x)=f(x_0)+f[x_0,x_1](x-x_0)=f_0+\frac{f_1-f_0}{x_1-x_0}(x-x_0)=-\frac{1}{x}+\frac{3}{2}\]

So,
\[\frac{f''(\xi(x))}{2}(x-1)(x-2)=f(x)-p_1(f;x)=\frac{1}{x}+\frac{x}{2}-\frac{3}{2}=\frac{(x-1)(x-2)}{2x}\]

Since \(f''(x)=\frac{2}{x^3}\), we get 
\[\xi(x)=\sqrt[3]{2x}\]

\subsection*{I-b}

$\xi(x)=\sqrt[3]{2x}$ increases on $[1,2]$. So $\max\xi(x)=\sqrt[3]{4}$ and $\min\xi(x)=\sqrt[3]{2}$.

$f''(\xi(x))=\frac{1}{x}$ decreases on $[1,2]$. So $\max f''(\xi(x))=1$.



\section*{II. Constructing Non-negative Polynomials}
\subsection*{II-a}

Since $f_i \geq 0$ for distinct $x_i,\ i=0,1,\cdots,n$, $\exists! q \in \mathbb{P}_n\ s.t.\ q(x_i)=\sqrt{f_i}$.

Take $p(x)=(q(x))^2$, then $p \in \mathbb{P}_{2n}^{+}$ and satisfies that $p(x_i)=(q(x_i))^2=f_i$.

$q$ can be found by interpolation. Thus, we can find $p$ for this problem.



\section*{III. Induction Proof for Exponential Function}
\subsection*{III-a}

For $f(x)=e^x$, we aim to show that for all $n \in \mathbb{Z}^{+}$:
\begin{equation}\label{3aim}
  \forall t \in \mathbb{R},\ f[t,t+1,\cdots,t+n]=\frac{(e-1)^n}{n!}e^t 
\end{equation}

When $n=1$, $f[t,t+1]=\frac{e^{t+1}-e^t}{t+1-t}=(e-1)e^t$, which satisfies \eqref{3aim}.

If \eqref{3aim} holds for $n$, then for $n+1$, 
\begin{align*}
  f[t,t+1,\cdots,t+n+1]&=\frac{f[t+1,t+2,\cdots,t+n+1]-f[t,t+1,\cdots,t+n]}{t+n-t} \\
  &=\frac{1}{n}(\frac{(e-1)^n}{n!}e^{t+1}-\frac{(e-1)^n}{n!}e^t) \\
  &=\frac{(e-1)^{n+1}}{(n+1)!}e^t \\
\end{align*}

So, \eqref{3aim} also holds for $n+1$. Thus, \eqref{3aim} is proved by induction.

\subsection*{III-b}

Substitute $t=0$ into \eqref{3aim} we get $f[0,1,\cdots,n]=\frac{(e-1)^n}{n!}$.

Since $f^{(n)}=e^x$, we get $\xi=\ln(e-1)^n=n\ln(e-1)$.

$\ln(e-1)>\frac{1}{2}$, and so $\xi$ is located to the right of the midpoint $\frac{n}{2}$.



\section*{IV. Newton's Interpolation and Minimum Estimation}
\subsection*{IV-a}
Construct the table of divided differ:
\[
\begin{array}{c|cccc}
  0 & 5 & & & \\
  1 & 3 & -2 & & \\
  3 & 5 & 1 & 1 & \\
  4 & 12 & 7 & 2 & 0.25 \\
\end{array}
\]

So, $p_3(f;x)=5-2(x-0)+1(x-0)(x-1)+0.25(x-0)(x-1)(x-3)=\frac{1}{4}x^3-\frac{9}{4}x+5$.

\subsection*{IV-b}
We use $p_3(x)$ to approximate $f(x)$. $p_3'(x)=\frac{3x^2-9}{4}$.

Thus on $(1,3)$, $p_3$ has a minimum point $x_{min}=\sqrt{3}$, giving an approximate value for $f$.



\section*{V. Divided Difference and Higher-order Derivatives}
\subsection*{V-a}
We have $f(x)=x^7,\ f'(x)=7x^6,\ f''(x)=42x^5$.

Then, $f[1,1]=f'(1)=6,\ f[1,1,1]=\frac{f''(1)}{2!}=21,\ f[2,2]=f'(2)=448$.

Construct the table of divided differ:
\[
\begin{array}{c|cccccc}
  0 & 0 & & & & & \\
  1 & 1 & 1 & & & & \\
  1 & 1 & 7 & 6 & & & \\
  1 & 1 & 7 & 21 & 15 & & \\
  2 & 128 & 127 & 120 & 99 & 42 & \\
  2 & 128 & 448 & 321 & 201 & 102 & 30 \\
\end{array}
\]

Thus, \(f[0,1,1,1,2,2]=30\).

\subsection*{V-b}
By \textbf{Corollary 2.22}, $\exists \xi \in (0,2)\ s.t.\ f^{(5)}(\xi)=5!f[0,1,1,1,2,2]=3600$.

$f^{(5)}(x)=7*6*5*4*3x^2=2520x^2 \Rightarrow \xi =\sqrt{\frac{10}{7}} \approx 1.195$



\section*{VI. Hermite Interpolation and Error Estimation}
\subsection*{VI-a}
Construct the table of divided differ:
\[
\begin{array}{c|ccccc}
  0 & 1 & & & & \\
  1 & 2 & 1 & & & \\
  1 & 2 & -1 & -2 & & \\
  3 & 0 & -1 & 0 & \frac{2}{3} & \\
  3 & 0 & 0 & \frac{1}{2} & \frac{1}{4} & -\frac{5}{36} \\
\end{array}
\]

So the interpolation polynomial $p(x)=1+1x-2x(x-1)+\frac{2}{3}x(x-1)^2-\frac{5}{36}x(x-1)^2(x-3)$.

Thus, $f(2) \approx p(2)=1+2-4+\frac{4}{3}+\frac{5}{18}=\frac{11}{18}$.

\subsection*{VI-b}
By \textbf{Corollary 2.22} and  \textbf{Theorem 2.21}, $\exists \xi(x) \in [0,3]\ s.t.$
\[\forall x \in [0,3],\ f(x)-p(x)=\frac{1}{5!}f^{(5)}(\xi(x))x(x-1)^2(x-3)^2\]

So the error of the above question $|f(2)-p(2)| \leq \frac{1}{120}M*2*1^2*1^2 = \frac{M}{60}$.



\section*{VII. Forward and Backward Differences}
We aim to prove for $x_j=x+jh$,
\begin{equation}\label{7aim1}
  \Delta^k f(x) = k! h^k f[x_0, x_1, \cdots, x_k]
\end{equation}
\begin{equation}\label{7aim2}
  \nabla^k f(x) = k! h^k f[x_0, x_{-1}, \cdots, x_{-k}]
\end{equation}

\subsection*{VII-a}
For $k=1$, we have $\Delta f(x)=f(x_1)-f(x_0)=h f[x_1,x_0]$, which satisfies \eqref{7aim1}.

If \eqref{7aim1} holds for $k$, then for $k+1$,
\begin{align*}
  \Delta^{k+1}f(x) &= \Delta^k f(x+h) - \Delta^k f(x) \\
  &= k! h^k f[x_1, x_2, \cdots, x_{k+1}] - k! h^k f[x_0, x_1, \cdots, x_k] \\
  &= k! h^k f[x_0, x_1, \cdots, x_{k+1}](x_{k+1}-x_0) \\
  &= (k+1)! h^{k+1} f[x_0, x_1, \cdots, x_{k+1}] \\
\end{align*}

So \eqref{7aim1} also holds for $k+1$. Thus, \eqref{7aim1} is proved by induction.

\subsection*{VII-b}
For $k=1$, we have $\nabla f(x)=f(x_0)-f(x_{-1})=hf[x_1,x_{-1}]$, which satisfies \eqref{7aim2}.

If \eqref{7aim2} holds for $k$, then for $k+1$,
\begin{align*}
  \nabla^{k+1}f(x) &= \nabla^k f(x) - \nabla^k f(x-h) \\
  &= k! h^k f[x_0, x_{-1}, \cdots, x_{-k}]-k!h^k f[x_{-1}, x_{-1}, \cdots, x_{-k-1}] \\
  &= k! h^k f[x_0, x_{-1}, \cdots, x_{-k-1}](x_0-x_{-k-1}) \\
  &= (k+1)! h^{k+1} f[x_0, x_{-1}, \cdots, x_{-(k+1)}] \\
\end{align*}

So \eqref{7aim2} also holds for $k+1$. Thus, \eqref{7aim2} is proved by induction.




\section*{VIII. Partial Derivatives of Divided Differences}
\subsection*{VIII-a}
\begin{align*}
    \frac{\partial}{\partial x_0} f[x_0, x_1, \cdots, x_n] 
    &= \lim_{h \to 0} \frac{f[x_0+h, x_1, \cdots, x_n]-f[x_0, x_1, \cdots, x_n]}{h} \\
    &= \lim_{h \to 0} f[x_0, x_1, \cdots, x_n, x_0+h] \\
    &= f[x_0, x_0, x_1, \cdots, x_n] \\
\end{align*}

By \textbf{Corollary 2.15} we reached this proof. And similarly we have:

\[\frac{\partial}{\partial x_k} f[x_0, x_1, \cdots, x_n]=f[x_0, x_1, \cdots, x_n, x_k]\]



\section*{IX. Min-Max Polynomial Optimization}
\subsection*{IX-a}
In \textbf{Corollary 2.48}, the equality can be achieved. So we have:

\[\min \max_{y \in [-1,1]} |y^n+b_1y^{n-1}+\cdots+b_n| \geq \frac{1}{2^{n-1}}\]

For $x \in [a,b]$ , take $x=\frac{b-a}{2}y+\frac{b+a}{2},\ y \in [-1,1]$. Then,
\begin{align*}
  \min \max_{x \in [a,b]} |a_0x^n+a_1x^{n-1}+\cdots+a_n| 
  &= \min \max_{y \in [-1,1]} \frac{|a_0|(b-a)^n}{2^n}|y^n+b_1y^{n-1}+\cdots+b_n| \\
  &= \frac{|a_0|(b-a)^n}{2^{2n-1}} \\
\end{align*}



\section*{X. Chebyshev Polynomial Transformation}
\subsection*{X-a}
We have
\[T_n(x)=\cos(n\arccos{x})\]
\[\|\hat{p}_n(x)\|_\infty=\max_{x \in [-1,1]}|\frac{T_n(x)}{T_n(a)}|=\frac{1}{|T_n(a)|}\]

By \textbf{Theorem 2.45}, $T_n(x)$ has extreme values $(-1)^k$ at $x_k'=\cos{\frac{k\pi}{n},\ k=0,1,\cdots,n}$.

Assume that $\exists p \in \mathbb{P}_n^a\ s.t.$
\[\ \|p\|_\infty<\|\hat{p}_n(x)\|_\infty=\frac{1}{|T_n(a)|}\]

Let \(Q(x)=\frac{T_n(x)}{T_n(a)}-p(x)\). Then,
\[Q(x_k')=\frac{(-1)^k}{T_n(a)}-p(x_k')\]

The assumption implies that $Q_n$ has alternating signs at these $n+1$ points. Plus, $Q(a)=1-p(a)=0$ for $a>1>x_k',\ \forall k=0,1,\cdots,n$

So $Q$ has at least $n+1$ zeros. Since the degree of $Q$ is at most $n$, we conclude that $Q=0$.

Then $p=\hat{p}_n(x)$ and we reach a contradiction. This completes the proof.



\section*{XI. Proof of Lemma 2.53}
For \[b_{n,k}(t):=\binom{n}{k} t^k (1-t)^{n-k},\ \ k = 0, 1, \cdots, n,\ \ t \in [0,1]\]

Show that \[ b_{n-1,k}(t)= \frac{n-k}{n} b_{n,k}(t)+\frac{k+1}{n} b_{n,k+1}(t)\].
\subsection*{XI-a}
We have two identities:
\begin{equation}\label{11_1}
  \frac{n-k}{n}\binom{n}{k}=\frac{(n-k)n!}{nk!(n-k)!}=\frac{(n-1)!}{k!(n-1-k)!}=\binom{n-1}{k}
\end{equation}
\begin{equation}\label{11_2}
  \frac{k+1}{n}\binom{n}{k+1}=\frac{(k+1)n!}{n(k+1)!(n-k-1)!}=\frac{(n-1)!}{k!(n-1-k)!}=\binom{n-1}{k}
\end{equation}

Then,
\[\binom{n-1}{k}=\frac{n-k}{n}\binom{n}{k}+t \left( \frac{k+1}{n}\binom{n}{k+1}-\frac{n-k}{n}\binom{n}{k} \right) =\frac{(1-t)(n-k)}{n}\binom{n}{k}+t\frac{k+1}{n}\binom{n}{k+1}\]

Thus,
\begin{align*}
  b_{n-1,k}(t) 
  &= \binom{n-1}{k}t^k(1-t)^{n-1-k} \\
  &= t^k(1-t)^{n-k}\frac{(n-k)}{n}\binom{n}{k}+t^{k+1}(1-t)^{n-1-k}\frac{k+1}{n}\binom{n}{k+1} \\
  &=\frac{n-k}{n} b_{n,k}(t)+\frac{k+1}{n} b_{n,k+1}(t) \\
\end{align*}



\section*{XII. Proof of Lemma 2.55}
Show that \[\int_{0}^{1} b_{n,k}(t) \, dt = \frac{1}{n+1}.\]
\subsection*{XII-a}
The Beta function $B(p, q)$ is defined as:
\[ B(p, q) = \int_0^1 t^{p-1} (1-t)^{q-1}dt,\ p>0,q>0\]

When $p$ and $q$ are positive integers, the Beta function can be expressed in terms of factorials:
\[ B(p, q) = \frac{\Gamma(p) \Gamma(q)}{\Gamma(p+q)} = \frac{(p-1)! (q-1)!}{(p+q-1)!} \]

Where $\Gamma$ is the Gamma function. 

Thus for this problem, we have:
\begin{align*}
  \int_0^1 b_{n,k}(t) &= \binom{n}{k}\int_0^1 t^k (1-t)^{n-k}dt \\
  &= \binom{n}{k}B(k+1,n-k+1) \\
  &= \binom{n}{k}\frac{k! (n-k)!}{(n+1)!} \\
  &= \frac{1}{n+1} \\
\end{align*}
\end{document}